package com.example.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
 *
 * 给定如下二叉树，以及目标和 sum = 22
 *
 *           5
 *          / \
 *         4   8
 *        /   / \
 *       11  13  4
 *      /  \      \
 *     7    2      1
 * 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
 */
public class Leetcode112_HasPathSum {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right = new TreeNode(8);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.right = new TreeNode(1);

        System.out.println(hasPathSum(root, 22));
    }

    /**
     * 递归
     * <p>
     * 是否存在从当前节点 root 到叶子节点的路径，满足其路径和为 sum。
     * <p>
     * 假定从根节点到当前节点的值之和为 val，
     * 我们可以将这个大问题转化为一个小问题：是否存在从当前节点的子节点到叶子的路径，满足其路径和为 sum - val。
     * <p>
     * 若当前节点就是叶子节点，那么我们直接判断 sum 是否等于 val 即可
     * （因为路径和已经确定，就是当前节点的值，我们只需要判断该路径和是否满足条件）。
     * <p>
     * 若当前节点不是叶子节点，我们只需要递归地询问它的子节点是否能满足条件即可。
     *
     * @param root
     * @param targetSum
     * @return
     */
    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null)
            return false;

        // 当前节点就是叶子节点，那么我们直接判断 sum == val
        if (root.left == null && root.right == null)
            return targetSum == root.val;

        // 不是叶子节点时，递归判断左右子树是否满足条件targetSum - root.val
        return hasPathSum(root.left, targetSum - root.val)
                || hasPathSum(root.right, targetSum - root.val);
    }

    /**
     * 使用广度优先搜索的方式，记录从根节点到当前节点的路径和，以防止重复计算。
     *
     * 使用两个队列，分别存储将要遍历的节点，以及根节点到这些节点的路径和即可
     * @param root
     * @param sum
     * @return
     */
    public static boolean hasPathSum2(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queNode = new LinkedList<TreeNode>();
        Queue<Integer> queVal = new LinkedList<Integer>();
        queNode.offer(root);
        queVal.offer(root.val);
        while (!queNode.isEmpty()) {
            TreeNode now = queNode.poll();
            int tmp = queVal.poll();
            if (now.left == null && now.right == null) {
                if (tmp == sum) {
                    return true;
                }
                continue;
            }
            if (now.left != null) {
                queNode.offer(now.left);
                queVal.offer(now.left.val + tmp);
            }
            if (now.right != null) {
                queNode.offer(now.right);
                queVal.offer(now.right.val + tmp);
            }
        }
        return false;
    }
}
